In various electrical/electronic applications such as a video conference, a high definition television, a receiver for a video on demand (VOD), a personal computer compatible with an MPEG (moving picture experts group) image, a game machine, a receiver for a ground wave digital broadcast, a receiver for a digital satellite broadcast and a cable television, an image signal is transmitted in a digitized form. However, in the process of changing an analog signal into a digitized form, the amount of the data is greatly increased. For the reason, it is inevitable to compress the digitized image data for a successful transmission thereof.
To compress the digitized image data, three methods are conventionally used: one is a method for reducing a temporal redundancy of the data; another is a method for reducing a spatial redundancy of the data; and the third is a method for decreasing a statistical redundancy by using characteristic of generated encoded data. Particularly, to reduce the temporal redundancy of the image data, a motion estimation and compensation technique is widely used in the majority of motion picture compression standards, e.g., MPEG and H. 263.
In the motion estimation and compensation technique, a portion that is the most similar to a certain part in a current frame (hereinafter, a best matching portion) is searched out from a reference frame, e.g., a previous frame or a next frame. Then, only the difference value between the certain part in the current frame and the best matching portion in the previous or the next reference frame is transmitted. Herein, it is understood that a precise estimation of a motion vector will reduce the difference value that should be transmitted, thereby effectively diminishing the transmission data. However, a considerable amount of calculations and time are required in order to find the best matching portion in the previous or the next frame. In fact, the motion estimation is the most time-consuming stage of all the stages performed for the encoding of the motion picture. Accordingly, there has been continuously made an effort to reduce the processing time for the motion estimation.
In the meanwhile, the motion estimation technique adopts two approaches in general; one is a pixel-by-pixel approach and the other is a block-by-block approach. Among these, the block-by-block estimation algorithm has gained a prominent popularity in the art.
According to the block-by-block estimation algorithm, a current frame is divided into a plurality of equal-sized search blocks. For a search block in the current frame, a best matching block is searched out from a search region within a previous frame. A motion vector, by definition, represents a displacement between the search block and the best matching block. The motion vector is encoded and then processed. In estimating a degree of matching between two blocks, various matching functions are employed. Among these, a method for obtaining a sum of absolute difference (SAD) between pixels in the two blocks is widely used.
A full-region search method is the simplest block-by-block estimation technique, where a SAD value is calculated at all possible search positions within a search region of a certain search block in the current frame. Then, a search position having the smallest SAD value is selected to thereby obtain a corresponding motion vector. Though this full-region search method has a merit in that a search mechanism is simple and an optimum motion vector can be effectively obtained, a real-time application of this method is very difficult because the amount of calculations are excessively large.
As a resolution to the drawbacks of the full-region search method described above, an array-structured motion estimation apparatus has been utilized. The array-structured motion estimating apparatus employs a plurality of processing elements (PE) arranged in parallel to each other to obtain an SAD value.
In the array-structured motion estimation process, a plurality of operations, e.g., a full-pixel searching operation, a half-pixel searching operation, an intra/inter mode determining operation, etc., is performed. Among these various operations involved, the full-pixel searching operation is the most time-consuming process, occupying about 60% of the whole processing time. Further, the full-pixel searching operation has been included in almost all the moving picture related standards adopted so far. Thus, a more efficient full-pixel search algorithm has been a key to a realization of a real-time encoding of the moving pictures. Accordingly, many researches have been made in various ways to develop a high efficiency full-pixel estimation algorithm.